home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group97b.txt / 000021_icon-group-sender _Thu Jul 10 14:19:02 1997.msg < prev    next >
Internet Message Format  |  2000-09-20  |  6KB
  1. Received: from kingfisher.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Thu, 10 Jul 1997 16:53:26 MST
  2. Received: by kingfisher.CS.Arizona.EDU; (5.65v3.2/1.1.8.2/08Nov94-0446PM)
  3.     id AA27195; Thu, 10 Jul 1997 16:53:25 -0700
  4. Message-Id: <199707102119.OAA00541@orpheus.gemini.edu>
  5. From: swampler@noao.edu (Steve Wampler)
  6. Date: Thu, 10 Jul 1997 14:19:02 MST
  7. X-Mailer: Mail User's Shell (7.2.3 5/22/91)
  8. To: icon-group@cs.arizona.edu
  9. Subject: Results of 'A small puzzle'
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11. Status: RO
  12.  
  13. The puzzle was to write a procedure lcp(s1,s2) that would return
  14. the longest common prefix of strings s1 and s2.
  15.  
  16. I won't repost the solutions that people have already sent to this
  17. group.  Instead, I'll give my own solutions and then show some timings.
  18.  
  19. --------- my solutions --------
  20. procedure lcp0(s1,s2)
  21.    return s2 ? =s1[1+:*s1 to 0 by -1]
  22. end
  23.  
  24. procedure lcp1(s1,s2)
  25.    return s2 ? =s1[1+:*(if *s1 > *s2 then s2 else s1) to 0 by -1]
  26. end
  27.  
  28. procedure lcp2(s1,s2)
  29.    return s1[1+:(p := *s1 to 0 by -1)] == s2[1+:p]
  30. end
  31.  
  32. procedure lcp3(s1,s2)
  33.    return s1[1+:(p := (many(s1**s2,s1)|0) to 0 by -1)] == s2[1+:p]
  34. end
  35. -------------------------------
  36.  
  37. In this list, the even-numbered procedures are 'simple', the odd
  38. numbered try out a couple of heuristics.
  39.  
  40. Now for some timings:
  41.  
  42. As you might imagine, the speed of each algorithm is
  43. extremely dependent on the nature of the input.  Factors that
  44. influence the speed depend include (a) the sizes of the two strings,
  45. (b) the length of the longest common prefix, (c) the order of
  46. the two strings given as arguments.  I didn't run any tests with
  47. *really* long strings - the linear solutions would have done
  48. much better on long strings with short lcp's.
  49.  
  50. There is no clearly superior solution.  I think the conclusion is
  51. that if you know the nature of the strings you are dealing with,
  52. you can pick an algorithm that does a good job with it!
  53.  
  54. I've wondered if one of the fast substring find algorithms that
  55. are available could be adopted to the lcp() problem, but didn't
  56. feel like trying to code one up, as I doubt they would
  57. help as much for prefix substrings as they do in the
  58. general case.
  59.  
  60. Also, you could produce a solution that *looks* really good
  61. according to my test program by doing something like:
  62.  
  63. # warning untested code follows!
  64. procedure lcp(s1,s2)
  65.     local k
  66.     static lcpTab
  67.     initial lcpTab := table()
  68.  
  69.     k := s1 || ":" || s2
  70.  
  71.     /lcpTab[k] := real_lcp(s1,s2)
  72.     return lcpTab[k]
  73. end
  74.  
  75. But that would be *cheating* and potentially very costly to
  76. use in practice...though there is a simpler cheat that
  77. at least isn't so potentially costly, even if it isn't likely
  78. to help in the Real World(tm).
  79.  
  80. --------------- Timing comparisons ---------------------------
  81. The two strings are shown at the start of each time set, separated
  82. by a :.
  83.  
  84. Results are ordered from fastest to slowest for each time set.
  85. Time is the total time for 50,000 calls to the routine, minus
  86. the loop overhead itself.
  87.  
  88. Multiple solutions from the same person are numbered in the
  89. same order that they appeared in their post.  (I.e. bob1()
  90. is the first solution by Bob, bob2() is the 2nd., etc.)
  91.  
  92. :        { two null strings }
  93. carl...........         3.633
  94. bob2...........         4.183
  95. bob1...........         4.183
  96. steve1.........         4.249
  97. lcp0...........         5.750
  98. lcp2...........         5.766
  99. lcp1...........         6.683
  100. jerry..........         6.733
  101. steve2.........         6.950
  102. steve3.........         7.033
  103. lcp3...........         8.000
  104.  
  105. fool:foodchain
  106. lcp0...........         7.550
  107. lcp1...........         8.384
  108. lcp2...........         9.167
  109. carl...........        10.084
  110. lcp3...........        12.100
  111. bob2...........        13.033
  112. bob1...........        13.734
  113. steve1.........        14.467
  114. jerry..........        16.334
  115. steve2.........        18.917
  116. steve3.........        26.467
  117.  
  118.  
  119. foodchain:fool
  120. lcp1...........         8.517
  121. jerry..........         8.550
  122. carl...........        10.084
  123. lcp3...........        12.084
  124. bob2...........        12.900
  125. bob1...........        13.700
  126. steve1.........        14.534
  127. lcp0...........        15.133
  128. steve2.........        20.284
  129. lcp2...........        21.117
  130. steve3.........        28.717
  131.  
  132.  
  133. aaaaaaaaaaaaaaab:aaaaaaaaaaaaaaac
  134. lcp0...........         8.384
  135. lcp1...........         9.301
  136. jerry..........         9.850
  137. lcp2...........        10.084
  138. lcp3...........        14.567
  139. carl...........        29.268
  140. steve2.........        30.251
  141. steve3.........        40.051
  142. bob2...........        44.850
  143. bob1...........        46.218
  144. steve1.........        49.634
  145.  
  146.  
  147. aardvarkseatsmallants:smallantsareeatenbylargeardvarks
  148. carl...........         5.283
  149. bob2...........         5.451
  150. bob1...........         5.650
  151. steve1.........         5.684
  152. steve3.........         9.234
  153. steve2.........        10.184
  154. lcp0...........        38.350
  155. lcp1...........        39.217
  156. jerry..........        57.800
  157. lcp2...........        71.933
  158. lcp3...........        78.284
  159.  
  160.  
  161. smallantsareeatenbylargeardvarks:aardvarkseatsmallants
  162. carl...........         5.284
  163. bob2...........         5.468
  164. steve1.........         5.684
  165. bob1...........         5.684
  166. steve3.........         9.217
  167. steve2.........        10.234
  168. lcp1...........        39.284
  169. jerry..........        40.617
  170. lcp0...........        54.868
  171. lcp3...........        68.851
  172. lcp2...........        98.450
  173.  
  174.  
  175. thisistheexactsamestringastheotherone:thisistheexactsamestringastheotherone
  176. lcp0...........         7.034
  177. lcp2...........         7.151
  178. lcp1...........         7.967
  179. jerry..........         8.101
  180. lcp3...........        14.651
  181. steve2.........        50.118
  182. carl...........        62.750
  183. steve3.........        77.267
  184. bob2...........        96.051
  185. bob1...........       103.884
  186. steve1.........       112.167
  187.  
  188. -----------------------------------------------------------
  189.  
  190. I think I had about as much fun working on the timing test program
  191. as I did on the puzzle itself!  If anyone would like to see the
  192. test program, let me know and I'll post it.  (Perhaps people would
  193. like to improve upon it...)
  194.  
  195. -- 
  196. Steve Wampler - swampler@gemini.edu [Gemini 8m Telescopes Project (under AURA)]
  197. O Sibile, si ergo, fortibus es inero.
  198. Nobile, demis trux.  Demis phulla causan dux.
  199.